class Solution
{
public:
    int cherryPickup(vector<vector<int>> &grid)
    {
        int n = grid.size();
        vector<vector<int>> nGrid(2 * n, vector(2 * n, -1));

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                nGrid[i][j] = grid[i][j];
                nGrid[n + i][n + j] = grid[i][j];
            }
        }
        nGrid[n - 1][n] = 0;

        int sum = moveStep(nGrid, 0, 0);

        if (sum == -1)
        {
            return 0;
        }
        else
        {
            return sum;
        }
    }

    int moveStep(vector<vector<int>> &grid, int i, int j)
    {
        if (grid[i][j] == -1)
        {
            return -1;
        }

        int n = grid.size() / 2;
        int t = -1;

        if (i < n && j < n)
        {
            t = grid[i][j];
            grid[i + n][j + n] = 0;
        }

        int moveDown = -1;
        int moveRight = -1;

        if (i == 2 * n - 1 && j == 2 * n - 1)
        {
            return grid[i][j];
        }

        if (i < 2 * n - 1)
        {
            moveDown = moveStep(grid, i + 1, j);
        }
        if (j < 2 * n - 1)
        {
            moveRight = moveStep(grid, i, j + 1);
        }

        if (i < n && j < n)
        {
            grid[i + n][j + n] = t;
        }

        if (moveDown == -1 && moveRight == -1)
        {
            return -1;
        }
        else
        {
            return max(moveDown, moveRight) + grid[i][j];
        }
    }
};